package sliding_window;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2024-01-18
 * Time:16:23
 * Text：串联所有单词的子串
 */
public class Text2 {
    public  static ArrayList<Integer> findSubstring(String S, String[] L) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        HashMap<String,Integer> map=new HashMap<>();
        for(String str:L){
            map.put(str,map.getOrDefault(str,0)+1);
        }
        int len=L[0].length(),m=L.length;
        for(int i=0;i<len;i++){
            HashMap<String,Integer> map1=new HashMap<>();
            for(int left=i,right=i,count=0;right+len<=S.length();right+=len){
                if(right-left+1>len*m){
                    String str2=S.substring(left,left+len);
                    if(map1.get(str2)<=map.getOrDefault(str2,0)){
                        count--;
                    }
                    map1.put(str2,map1.get(str2)-1);
                    left+=len;
                }

                String str1=S.substring(right,right+len);
                map1.put(str1,map1.getOrDefault(str1,0)+1);
                int num=map.getOrDefault(str1,0);
                if(map1.get(str1)<=map.getOrDefault(str1,0)){
                    count++;
                }

                if(count==m){
                    list.add(left);
                }
            }
        }
        return list;
    }

    public static void main(String[] args) {
        String str="wordgoodgoodgoodbestword";
        String[] str1={"word","good","best","good"};
        System.out.println(findSubstring(str,str1));
    }
}